rbtree: optimize rb_erase()
authorWolfram Strepp <wstrepp@gmx.de>
Tue, 20 Jun 2017 12:50:13 +0000 (14:50 +0200)
committerJan Beulich <jbeulich@suse.com>
Tue, 20 Jun 2017 12:50:13 +0000 (14:50 +0200)
commite4b6d67ccd13a50997eade84ce37b47e1ed50b77
tree206686b49ba786518e8df7f6d5989bc5d73cc863
parentb2f178fb3576d459abbb0a0db14781003d4b01c5
rbtree: optimize rb_erase()

Tfour 4 redundant if-conditions in function __rb_erase_color() in
lib/rbtree.c are removed.

In pseudo-source-code, the structure of the code is as follows:

if ((!A || B) && (!C || D)) {
.
.
.
} else {
if (!C || D) {//if this is true, it implies: (A == true) && (B == false)
if (A) {//hence this always evaluates to 'true'...
.
}
.
//at this point, C always becomes true, because of:
__rb_rotate_right/left();
//and:
other = parent->rb_right/left;
}
.
.
if (C) {//...and this too !
.
}
}

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 55a63998b8967615a15e2211ba0ff3a84a565824]

Ported to Xen.

Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com>
Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com>
Acked-by: Jan Beulich <jbeulich@suse.com>
xen/common/rbtree.c